package com.cuz.daileetcode.bat100;

public class 子数组最大累加和 {


    public static int solution1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int len = arr.length;
        int pre = arr[0];
        int ans = arr[0];
        for (int i = 1; i < len; i++) {
            pre = Math.max(pre + arr[i], arr[i]);
            ans = Math.max(pre, ans);
        }
        return ans;
    }
    public static int maxSubArray2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        int preSum = 0;
        //left 到达right表示取一个数
        while (left <= right && right < nums.length) {
            //加上新的数
            preSum += nums[right++];
            //小于0===> -2 0  1  2  right=1
            //1 -1 2 left=1 nums[left] < 0
            //贪心的思想如果前面都小于0了 或者left处的数小于0了 为什么不舍弃这些数昵
            while ((preSum < 0 || nums[left] < 0) && left + 1 < right) {
                preSum -= nums[left];
                left++;
            }
            maxSum = Math.max(maxSum, preSum);
        }
        return maxSum;
    }
}
